package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/15 9:30
 */

import java.util.*;

/**
 * 中等题
 * 有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
 *
 * 给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自恰（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
 *
 * 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
 * 输出：[5,5,2,5,4,5,6,7]
 * 解释：
 * answer[0] = 5，
 * person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
 * 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
 * 但是目前还不清楚他是否比 person 0 更有钱。
 * answer[7] = 7，
 * 在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
 * 最安静（有较低安静值 quiet[x]）的人是 person 7。
 * 其他的答案也可以用类似的推理来解释。
 */
public class Demo_85_No851 {

    static int[] quietTemp;
    static int[][] richTemp;
    static Map<Integer,List<Integer>> mapTemp;

    public static void main(String[] args) {


        int m = 01011;
        System.out.println(m);

//        richTemp = new int[][]{{0,5},{0,6},{0,7},{0,8},{0,9},{1,4},{1,5},{1,7},{1,8},{2,3},{2,4},{2,6},{2,8},{3,5},{3,7},{3,8},{4,6},{4,7},{4,8},{5,7},{6,7},{6,8},{7,9},{8,9}};
//        //{5,1,9,3,8,6,7,2,0,4}
//        quietTemp = new int[]{5,1,9,3,8,6,7,2,0,4};
//        System.out.println(Arrays.toString(loudAndRich(richTemp, quietTemp)));
    }

    public static int[] loudAndRich(int[][] richer, int[] quiet) {

        Map<Integer,List<Integer>> mapTemp = new HashMap<>();
        for (int i = 0; i < quiet.length; i++) {
            mapTemp.put(i,new ArrayList<>());
        }
        for (int i = 0; i < richer.length; i++) {
            if(!mapTemp.get(richer[i][1]).contains(richer[i][0])){
                mapTemp.get(richer[i][1]).add(richer[i][0]);
            }
        }
        int[] ans = new int[quiet.length];
        int max =  -1;

        for (int i = 0; i < quiet.length; i++) {
            List<Integer> integers = mapTemp.get(i);
            if(integers.size()==0) ans[i] = i;
            else{
                max = integers.get(0);
                for (int j = 0; j < integers.size(); j++) {
                    if(quiet[integers.get(j)]<quiet[max]){
                        max = integers.get(j);
                    }
                }
                ans[i] = max;
            }
        }
        for (int i = 0; i < ans.length; i++) {
            int temp = ans[i];
            int tmp = ans[ans[i]];
            while(temp!=tmp){
                if(quiet[temp]>quiet[tmp]) {
                    ans[i] = ans[tmp];
                }
                temp = ans[i];
                tmp = ans[ans[tmp]];
            }
            if(quiet[ans[i]]>quiet[i]){
                ans[i] = i;
            }

        }
        return ans;
    }

}
